#include <unordered_map>
#include <utility>
#include <algorithm>
using namespace std;
class TimeMap
{
private:
    /* data */
    std::unordered_map<std::string,std::vector<std::pair<int,std::string>>> m;

public:
    TimeMap(/* args */);
    ~TimeMap();
    void set(string key,string value,int timestamp)
    {
        m[key].emplace_back(timestamp,value);//往m中插入kv
    }
    string get(string key,int timestamp)
    {
        auto &pairs = m[key];
        // 使用一个大于所有 value 的字符串，
        //以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置
        pair<int,string> p={timestamp,string{127}};
        //在pairs 中找到第一个不小于p timestamp 的pair
        auto i = upper_bound(pairs.begin(), pairs.end(), p);
        if (i!=pairs.begin())
        {
            return (i-1)->second;
        }
        return "";
    }
};
//解法2
class TimeMap2 {
    int kvCnt;
    vector<int> timeSeq;
    vector<string> valSeq;
    unordered_map<string,vector<int>> HashMap;
public:
    /** Initialize your data structure here. */
    TimeMap2(): kvCnt(0) {}
    
    void set(string key, string value, int timestamp) {
        timeSeq.push_back(timestamp);
        valSeq.push_back(value);
        HashMap[key].push_back(kvCnt++);
    }
    
    string get(string key, int timestamp) {
        if(kvCnt == 0 || HashMap.count(key) == 0)
            return "";

        auto& vec = HashMap[key];
        int idx1 = upper_bound(timeSeq.begin(), timeSeq.end(), timestamp) - timeSeq.begin();
        int idx2 = lower_bound(vec.begin(), vec.end(), idx1) - vec.begin();

        return idx2 > 0 ? valSeq[vec[idx2 - 1]] : "";
    }
};